\documentclass[a4paper]{article}

\usepackage{color}
\usepackage{hyperref}
\usepackage{xltxtra}
\usepackage{multirow}
\usepackage{fancyhdr}
\usepackage{array}
\usepackage{xeCJK}
\usepackage{float}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{amsmath}
\usepackage[subsection]{algorithm}
\usepackage{algorithmic}
\DeclareGraphicsExtensions{.pdf,.png,.jpg}

\hypersetup{
colorlinks=true,
linkcolor=black,
unicode=true
}

\setCJKmainfont{微软雅黑}
\setromanfont[Mapping=tex-text]{Consolas}
\XeTeXlinebreaklocale "zh"                      
\XeTeXlinebreakskip = 0pt plus 1pt minus 0.1pt  
\linespread{1.5}       

\everymath{\displaystyle}          

% Margins
\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\pagestyle{fancy}
\lhead{}
\chead{并行计算}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}



%------------------------------------------------------------------
%                lstlisting definition
%------------------------------------------------------------------

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

\lstset{ %
  backgroundcolor=\color{white},   % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  captionpos=b,                    % sets the caption-position to bottom
  commentstyle=\color{mygreen},    % comment style
  deletekeywords={...},            % if you want to delete keywords from the given language
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,                    % adds a frame around the code
  keywordstyle=\color{blue},       % keyword style
  language=C,                 	   % the language of the code
  morekeywords={*,...},            % if you want to add more keywords to the set
  numbers=left,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showspaces=false,                 % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=2,                    % the step between two line-numbers. If it's 1, each line will be numbered
  stringstyle=\color{mymauve},     % string literal style
  tabsize=4,                       % sets default tabsize to 2 spaces
  title=\lstname                   % show the filename of files included with \lstinputlisting; also try caption instead of title
}




\begin{document}


%----------------------------------------------------------------------------------------
%	Title Page
%----------------------------------------------------------------------------------------

\begin{titlepage}

\newcommand{\HRule}{\rule{\linewidth}{0.5mm}} % Defines a new command for the horizontal lines, change thickness here

\center % Center everything on the page
 
%----------------------------------------------------------------------------------------
%	HEADING SECTIONS
%----------------------------------------------------------------------------------------
\textsc{\LARGE Huazhong University \\ Of Science And Technology}\\[1.0cm]
\includegraphics[scale=1]{logo.png}\\[2.0cm] % Include a department/university logo - this will require the graphicx package
\textsc{\Large 并行计算复习资料}\\[1.0cm] % Major heading
% such as course name

%----------------------------------------------------------------------------------------
%	TITLE SECTION
%----------------------------------------------------------------------------------------

\HRule \\[0.4cm]
{ \huge \bfseries 2012-2013学年并行计算考试复习资料}\\[0.4cm] % Title of your document
\HRule \\[1.5cm]
 
%----------------------------------------------------------------------------------------
%	AUTHOR SECTION
%----------------------------------------------------------------------------------------

\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\emph{作者:}\\
徐峥\\
\end{flushleft}
\end{minipage}
~
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
\emph{导师:} \\
\textsc{路志宏\\    数学与统计学院} % Supervisor's Name
\end{flushright}
\end{minipage}\\[4cm]

% If you don't want a supervisor, uncomment the two lines below and remove the section above
%\Large \emph{Author:}\\
%John \textsc{Smith}\\[3cm] % Your name

%----------------------------------------------------------------------------------------
%	DATE SECTION
%----------------------------------------------------------------------------------------

{\large \today}\\[3cm] % Date, change the \today to a set date if you want to be precise


%----------------------------------------------------------------------------------------

\vfill % Fill the rest of the page with whitespace

\end{titlepage}
\newpage

\setcounter{tocdepth}{3}
{\pagestyle{plain}
\tableofcontents
\cleardoublepage}
\newpage

\section{基本概念与术语}
\label{sec:notion}
\paragraph{结点}
在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。
\paragraph{互联网络}
互联网络（Internet）是一种把许多网络都连接在一起的国际性网络，是最高层次的骨干网络。
\paragraph{内存}
内存是计算机中重要的部件之一，它是与CPU进行沟通的桥梁。
\paragraph{进程}
进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。
\paragraph{进程间通信}
进程间通信就是在不同进程之间传播或交换信息。
\paragraph{线程}
线程（thread, 台湾称执行绪）是"进程"中某个单一顺序的控制流。也被称为轻量进程（lightweight processes）。
\paragraph{指针}
在信息工程中指针是一个用来指示一个内存地址的计算机语言的变量。
\paragraph{同步}
同步(synchronous;sync;synchronism;synchronization)
指两个或两个以上随时间变化的量在变化过程中保持一定的相对关系。
\paragraph{广播}
一个数据帧或包被传输到本地网段 （由广播域定义）上的每个节点就是广播
\paragraph{归约}
归约是使用解决其它问题的"黑盒"来解决另一个问题.
\paragraph{流水线}
流水线是在一定的线路上连续输送货物搬运机械，又称输送线或者输送机。
\paragraph{通信}
通信，指人与人或人与自然之间通过某种行为或媒介进行的信息交流与传递，从广义上指需要信息的双方或多方在不违背各自意愿的情况下无论采用何种方法，使用何种媒质，将信息从某方准确安全传送到另方。
\paragraph{并发}
在操作系统中，是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一个时刻点上只有一个程序在处理机上运行。
\paragraph{并行计算机类型}
广义上的大类划分：
\begin{enumerate}
  \item 多核计算(Multicore computing)
  \item 对称多处理(Symmetric multiprocessing)
  \item 分布式计算(Distributed computing)
  \item 集群计算(Cluster computing)
  \item 大规模并行计算(Massive parallel processing)
  \item 网格计算(Grid computing)
\end{enumerate}
一些特殊的应用：
\begin{enumerate}
  \item 基于FPGA的可重构计算(Reconfigurable computing with field-programmable gate
  arrays)
  \item 基于GPU的通用目的计算(General-purpose computing on graphics processing units)
  \item 基于应用的集成芯片(Application-specific integrated circuits)
  \item 向量处理器(Vector processors)
\end{enumerate}
\textbf{Remark}:  这个题我找不到中文的资料，英文来自于Wikipedia, 中文翻译是我自己的理解。
\paragraph{拓扑结构}
计算机网络拓扑结构是指网络中各个站点相互连接的形式，在局域网中明确一点讲就是文件服务器、工作站和电缆等的连接形式。

\section{算法设计与实现}
\label{sec:algorithm}
\subsection{并行计算中常有技术的综述}
\label{ssec:exer1}
\paragraph{Remark} 开放题，答案略。
\subsection{多项式加法和乘法的串行算法及并行算法方案}
\label{ssec:exer2}
\subsubsection{多项式加法的串行与并行算法}
\begin{align*}
& a(x) = a_0 + a_1x + a_2x^2 \cdots + a_nx^n\\ 
& b(x) = b_0 + b_1x + b_2x^2 \cdots + b_mx^m
\end{align*}
他们的和式$c(x) = a(x)+b(x)$是$l = \max\{m,n\}$次多项式，故
\begin{align*}
& c_0 = a_0+b_0\\
& c_1 = a_1+b_1\\
& \ldots\\
& \ldots\\
& c_k = a_k+b_k
\end{align*}
\begin{algorithm}[H]                      
\caption{多项式加法的串行算法}          
\label{alg:polyadd_s}                           
\begin{algorithmic}                  
	\REQUIRE A(0:n), B(0:m)
	\ENSURE  C(0:l)
	\STATE l=(m>n)?m:n, A(n+1:l)=0, B(m+1:l)=0
	\FOR {k = 0 to l}
		\STATE $c_k = a_k+b_k$
	\ENDFOR
\end{algorithmic}
\end{algorithm}
本算法只有一个FOR循环，故并行化算法容易通过并行该FOR循环实现。
\begin{algorithm}[H]                      
\caption{多项式加法的并行算法}          
\label{alg:polyadd_p}                           
\begin{algorithmic}                  
	\REQUIRE A(0:n), B(0:m)
	\ENSURE  C(0:l)
	\STATE l=(m>n)?m:n, A(n+1:l)=0, B(m+1:l)=0
	\FOR {k = 0 to l in parallel}
		\STATE $c_k = a_k+b_k$
	\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsubsection{多项式乘法的串行与并行算法}
\begin{align*}
& a(x) = a_0 + a_1x + a_2x^2 \cdots + a_nx^n\\ 
& b(x) = b_0 + b_1x + b_2x^2 \cdots + b_mx^m
\end{align*}
则它们的乘积$c(x) = a(x)b(x)$是$m\times n$次多项式。且
\begin{align*}
& c_0 = a_0b_0\\
& c_1 = a_0b_1 + a_1b_0\\
& \ldots\\
& \ldots\\
& c_k = \sum\limits_{j=0}^{k} a_jb_{k-j}
\end{align*}
\begin{algorithm}[H]                      
\caption{多项式乘法的串行算法}          
\label{alg:polymul_s}                           
\begin{algorithmic}                  
	\REQUIRE A(0:n), B(0:m)
	\ENSURE  C(0:m+n)
	\STATE A(n+1:m+n) = 0, B(m+1:m+n) = 0
	\FOR {k = 0 to m+n}
		\FOR {j = 0 to k}
			\STATE $c_k = c_k + a_jb_{k-j}$
		\ENDFOR
	\ENDFOR
\end{algorithmic}
\end{algorithm}
注意到只有外层循环可以并行，故并行算法如下：
\begin{algorithm}[H]                      
\caption{多项式乘法的并行算法}          
\label{alg:polymul_p}                           
\begin{algorithmic}                  
	\REQUIRE A(0:n), B(0:m)
	\ENSURE  C(0:m+n)
	\STATE A(n+1:m+n) = 0, B(m+1:m+n) = 0
	\FOR {k = 0 to m+n in parallel}
		\FOR {j = 0 to k}
			\STATE $c_k = c_k + a_jb_{k-j}$
		\ENDFOR
	\ENDFOR
\end{algorithmic}
\end{algorithm}



\subsection{线性方程组（用于稠密线性方程组）的串行算法，并行化方法}
\subsubsection{全选主元的Gauss消元法}
串行算法的伪代码：

\subsubsection{列选主元的Gauss-Jordan消元法}
\subsubsection{LU分解法}

\subsection{线性方程组的迭代法并行化}
\subsection{分治法的优化及并行化方案}
一个问题被分成几个子问题，先求出子问题的解，然后进一步处理这些子问题的解，从而得到整个问题的解的方法，叫做分治法。
\subsection{插值多项式并行算法设计}
假定函数$f(x)$在一些给定的点x上的值是已知的。
如$(x_0, f_0), (x_1, f_1), \ldots, (x_n,
f_n)$。则试图构造关于$x$的$n$次多项式$f(x)$，且满足$f(x_i) = f_i$。\\
考虑多项式
\begin{align*}
P_k (x) = \frac{(x-x_0)(x-x_1)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n)}
{(x_k-x_0)(x_k-x_1)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)}
\end{align*}
则我们可以得到如下多项式：
\begin{align*}
& f(x) = f_0P_0(x) + f_1P_1(x) + \cdots + f_nP_n(x) \\
& f(x_i) = f_i 
\end{align*}
该公式称为Lagrange公式。
\begin{algorithm}[H]                      
\caption{Lagrange插值的并行算法}          
\label{alg:lagrangeint}                           
\begin{algorithmic}                  
    \REQUIRE x(1:n), f(1:n), y
    \ENSURE  $f_y$
    \FOR {k = 1 to n in parallel}
    	\STATE $P_k = 1$
    	\FOR {i = 1 to n}
    		\IF {$i \neq k$}
    			\STATE $P_k = P_k * (y-x_i)/(x_k - x_i)$
    		\ENDIF
    	\ENDFOR
    \ENDFOR
    \STATE $f_y = 0$
    \FOR {i = 1 to n in parallel}
    	\STATE $f_y = f_y + P_if_i$
    \ENDFOR
\end{algorithmic}
\end{algorithm}
\subsection{线性最小二乘问题并行算法}
\subsection{并行FFT算法}
\subsection{热传导方程的并行化}
定义热传导方程如下：
\begin{align*}
& u_t = au_{xx}\\
& u(x_0, t) = g_1(t)\\
& u(x_1, t) = g_2(t)\\
& u(x, t_0) = f(x)\\
\end{align*}
令时间方向($t$)上的步长$\tau$, 空间方向($x$)上的步长$h$，定义网比$r=\frac{a\tau}{h^2}$。
则可用Schmidt公式求解：
\begin{align*}
u_j^{k+1} = (1-2r)u_{j}^{k} + r(u_{j-1}^k + u_{j+1}^k)
\end{align*}
其中，$u_j^k = u(x_j, t_k)$。
则该方法的并行化算法可描述如下：
\begin{algorithm}[H]                      
\caption{热传导方程的并行算法}          
\label{alg:heatflow}                           
\begin{algorithmic}                  
    \REQUIRE $f(x), g_1(t), g_2(t), t_0, t_1, x_0, x_1, m, n$
    \STATE $h = (x_1 - x_0)/m, \tau = (t_1 - t_0)/n, r = a\tau/h^2$
    \STATE 初始化时间初值条件：
    \FOR{j = 1 to m in parallel} 
    	\STATE $x_j = x_0 + jh$
    	\STATE $u_j^0 = f(x_j)$
    \ENDFOR
    \STATE 初始化空间边值条件：
    \FOR{k = 1 to n in parallel} 
    	\STATE $t_k = t_0 + k\tau$
    	\STATE $u_0^k = g_1(t_k)$
    	\STATE $u_m^k = g_2(t_k)$
    \ENDFOR
    \STATE 运用Schmidt公式求解：
    \FOR{k = 1 to n}			 
		\FOR {j = 1 to m-1 in parallel}
			\STATE $u_j^{k} = (1-2r)u_j^{k-1} + r(u_{j-1}^{k-1} + u_{j+1}^{k+1})$
		\ENDFOR
    \ENDFOR
\end{algorithmic}
\end{algorithm}
\subsection{简单CUDA C程序的编写}
	
\section{声明}
本文档是一个初步的，仍在继续完善的文档。作者不保证其正确性及可靠性。如发现谬误请保持宽容和谅解并告知作者。
文档最新版本PDF和\LaTeX 源码可在如下地址被找到：\url{https://code.google.com/p/hust-mars/}。

\end{document}